package listbyorder.access101_200.test146;

import java.util.HashMap;

/**
 * 手写LRU缓存结构
 *
 * @author code_yc
 * @version 1.0
 * @date 2020/6/12 9:03
 */
public class Solution1 {

    // 维护一个节点类
    class Node {
        int val;
        Node last;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    // 维护一个双向链表
    class DoubleLinkedList {
        Node head;
        Node tail;

        public DoubleLinkedList() {
            this.head = null;
            this.tail = null;
        }

        // 向链表中添加元素
        public void addNode(Node node) {
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                node.last = tail;
                tail = node;
            }
        }

        // 将节点移动到尾部，表示最进行使用的元素
        public void moveNodeToTail(Node node) {
            if (tail == node) return;
            if (head == node) {
                head = head.next;
                head.last = null;
            } else {
                node.last.next = node.next;
                node.next.last = node.last;
            }
            tail.next = node;
            node.last = tail;
            node.next = null;
            tail = node;
        }

        // 将队列中的头节点删除
        public Node removeHead() {
            if (head == null) return null;
            Node res = head;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
                res.next = null;
            }
            return res;
        }
    }

    class LRUCache {

        HashMap<Integer, Node> keyNodeMap;
        HashMap<Node, Integer> nodeKeyMap;
        DoubleLinkedList nodeList;
        int capacity;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            keyNodeMap = new HashMap<>();
            nodeKeyMap = new HashMap<>();
            nodeList = new DoubleLinkedList();
        }

        int get(int key) {
            int res = -1;
            if (keyNodeMap.containsKey(key)) {
                Node cur = keyNodeMap.get(key);
                res = cur.val;
                nodeList.moveNodeToTail(cur);
            }
            return res;
        }

        void put(int key, int value) {
            if (keyNodeMap.containsKey(key)) {
                Node cur = keyNodeMap.get(key);
                cur.val = value;
                nodeList.moveNodeToTail(cur);
            } else {
                Node cur = new Node(value);
                if (keyNodeMap.size() == capacity) {
                    Node removeNode = nodeList.removeHead();
                    int removeKey = nodeKeyMap.get(removeNode);
                    keyNodeMap.remove(removeKey);
                    nodeKeyMap.remove(removeNode);
                }
                nodeList.addNode(cur);
                keyNodeMap.put(key, cur);
                nodeKeyMap.put(cur, key);
            }
        }
    }
}
